package leetcode_700;

import java.util.Arrays;
import java.util.Comparator;

/**
 *@author 周杨
 *MaximumLengthOfPairChain_646 给定n个区间 问n个区间能构成不重复区间的链表最大长度
 *describe:排序后用动态规划 AC 47%
 *2018年9月26日 上午11:53:55
 */
public class MaximumLengthOfPairChain_646 {
	
	public static void main(String[] args) {
		MaximumLengthOfPairChain_646 test=new MaximumLengthOfPairChain_646();
		System.out.println(test.findLongestChain(new int[][] {{1,2},{3,4},{2,3}}));
	}
	
	public int findLongestChain(int[][] pairs) {
		Arrays.sort(pairs,new Comparator<int []>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0]-o2[0];
			}
		});
        int dp[]=new int[pairs.length];
        dp[0]=1;
        for(int i=1;i<pairs.length;++i) {
        	dp[i]=1;
        	for(int j=0;j<i;++j) {
        		if(pairs[i][0]>pairs[j][1]) {
        			dp[i]=Math.max(dp[i],dp[j]+1);
        		}
        	}
        }
        return  dp[pairs.length-1];
    }
}
